package com.aqie.arithmetic.datastructure;

import edu.princeton.cs.algs4.SequentialSearchST;

/**
 * 基于拉链法的散列表
 * TreeMap : 红黑树
 * HashMap ：拉链法散列表
 */
public class SeparateChainingHashST<Key, Value> {
    // 键值对总数
    private int N;

    // 散列表的大小
    private int M;

    // 存放链表对象的数组
    private SequentialSearchST<Key, Value>[] st;

    public SeparateChainingHashST(){
        this(997);
    }

    public SeparateChainingHashST(int N){
        // 创建M条链表
        this.M = M;
        st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
        for (int i = 0; i < M; i++){
            st[i] = new SequentialSearchST<>();
        }
    }

    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public Value get(Key key){
        return (Value)st[hash(key)].get(key);
    }

    public void put(Key key, Value value){
        st[hash(key)].put(key, value);
    }

    public Iterable<Key> keys(){
        // 3.4.19 todo
        return null;
    }
}
